package niuke;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2023-04-22
 * Time: 10:07
 */
public class Soulution9 {
    public static void main(String[] args) {
        int [] arr = {3,7,6,5,4,3,2,1};
        quickSort(arr, 0, arr.length-1);
        System.out.println( Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int left, int right) {
        if( left >= right) return ;
        int pav = parviton( arr, left, right);
        quickSort( arr, left, pav-1);
        quickSort( arr, pav+1, right);
    }

    private static int parviton(int[] arr, int low, int high) {
        int tmp = arr[low];
        while( low < high){
            while(  low < high && tmp <= arr[high]){
                high--;
            }
            arr[low] = arr[high];
            while( low < high && tmp >= arr[low]){
                low++;
            }
            arr[high] =  arr[low];
        }
        arr[low] = tmp;
        return low;
    }
}
